
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def show(l, msg):
    print(msg)
    while l:
        print(l.val, sep='\n', end=' ')
        l = l.next
    print()


class Solution:
    """
    @param headA: the first list
    @param headB: the second list
    @return: a ListNode
    """
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None

        tail = self.tail(headA)
        tail.next = headB

        begin = self.cycle_begin(headA)
        tail.next = None
        return begin

    def tail(self, node):
        while node.next:
            node = node.next

        return node

    def has_cycle(self, node):
        slow, fast = node, node

        slow_dis = 0
        while fast and fast.next:       # 如果fast为null, 则不会再执行and之后的fast.next
            slow_dis += 1
            slow = slow.next
            fast = fast.next.next       # 可能取None/Swallow

            if slow is fast:
                # slow.show_v()
                print('slow_dis is [%s]' % slow_dis)
                return slow

        return None

    def cycle_begin(self, node):
        meet_node = self.has_cycle(node)
        if not meet_node:
            return None

        n1 = node
        n2 = meet_node
        dis = 0
        while n1 != n2:
            dis += 0
            n1, n2 = n1.next, n2.next

        return n1


def build_link_list():
    l5 = ListNode(5, None)
    l4 = ListNode(4, l5)
    l3 = ListNode(3, l4)
    l2 = ListNode(2, l3)
    l1 = ListNode(1, l2)

    l13 = ListNode(2, l5)
    l12 = ListNode(2, l13)
    l11 = ListNode(1, l12)

    return l1, l11

def main():
    print("start main")
    s = Solution()
    l1, l2 = build_link_list()
    # l2 = build_link_list2()

    n = s.getIntersectionNode(l1, l2)
    if n:
        print(n.val)


if __name__ == "__main__":
    main()


